package com.fr.lintcode;

import java.util.Arrays;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月28日
*时间：下午5:37:42
*/
public class Q183 {
    /** 
     *@param L: Given n pieces of wood with length L[i]
     *@param k: An integer
     *return: The maximum length of the small pieces.
     */
    public int woodCut(int[] L, int k) {
        if (L == null || L.length == 0) {
            return 0;
        }
        Arrays.sort(L);
        long max = L[L.length - 1];
        if (k <= 1) {
            return new Long(max).intValue();
        }
        long trueLen = 0;
        long min = 1;
        long len = -1;
        while (min <= max) {
            len = (min + max) / 2;
            long count = calculate(L, len);
            if (count >= k) {
                trueLen = len;
                min = len + 1;
            } else {
                max = len - 1;
            }
        }
        return new Long(trueLen).intValue();
    }

    private long calculate(int[] L, long len) {
        long count = 0;
        for (int i : L) {
            count += i / len;
        }
        return count;
    }

    @Test
    public void testA() {
        int[] L = { 6, 6, 5, 5, 6, 5, 4, 4, 5, 6, 6, 6, 5, 4, 5, 6, 5, 6, 4, 4, 4, 4, 6, 4, 5, 5, 4, 6, 6, 6, 6, 4, 6, 4, 4, 5, 6, 5, 5, 4, 6, 4, 6, 4, 4, 6,
                4, 5, 6, 5, 6, 6, 5, 4, 4, 5, 6, 4, 5, 5, 5, 6, 6, 4, 4, 5, 5, 6, 5, 5, 6, 4, 6, 4, 5, 6, 4, 4, 4, 6, 4, 6, 4, 5, 4, 6, 5, 6, 6, 5, 4, 4, 6, 5,
                6, 5, 6, 4, 4, 6, 4, 6, 5, 4, 4, 4, 4, 6, 6, 4, 6, 6, 6, 5, 4, 4, 6, 4, 4, 4, 5, 4, 6, 4, 6, 6, 4, 5, 6, 5, 6, 5, 4, 5, 5, 5, 4, 6, 5, 4, 5, 6,
                4, 4, 6, 6, 5, 6, 6, 4, 6, 5, 6, 5, 4, 6, 4, 6, 4, 6, 5, 6, 4, 6, 6, 4, 5, 4, 6, 6, 5, 6, 6, 5, 4, 4, 4, 4, 4, 5, 5, 4, 6, 5, 4, 6, 4, 6, 5, 6,
                6, 5, 4, 5, 6, 4, 4, 6, 5, 5, 6, 6, 6, 4, 6, 6, 5, 6, 5, 4, 6, 5, 4, 6, 5, 6, 4, 5, 4, 4, 5, 4, 5, 6, 6, 4, 4, 4, 4, 6, 6, 6, 6, 6, 5, 5, 4, 4,
                5, 5, 6, 6, 5, 6, 6, 6, 4, 5, 5, 4, 6, 4, 6, 4, 4, 6, 5, 6, 6, 6, 5, 4, 4, 4, 6, 4, 6, 4, 5, 6, 6, 4, 5, 6, 6, 6, 6, 6, 4, 5, 6, 4, 4, 4, 4, 5,
                5, 5, 6, 5, 5, 5, 4, 4, 5, 6, 6, 4, 6, 6, 6, 4, 5, 4, 6, 5, 6, 5, 5, 6, 5, 4, 5, 4, 6, 4, 5, 5, 5, 5, 5, 5, 4, 5, 5, 6, 4, 5, 6, 5, 6, 5, 6, 4,
                4, 5, 6, 5, 6, 6, 6, 5, 4, 5, 4, 6, 6, 6, 6, 4, 5, 5, 4, 5, 5, 5, 4, 6, 5, 5, 4, 6, 5, 6, 6, 6, 4, 4, 4, 6, 4, 6, 6, 4, 5, 4, 5, 6, 6, 6, 5, 6,
                4, 6, 6, 5, 6, 5, 6, 4, 4, 6, 4, 6, 5, 6, 6, 5, 4, 6, 5, 6, 6, 5, 6, 6, 4, 6, 6, 5, 6, 5, 6, 4, 5, 5, 5, 6, 6, 4, 5, 4, 4, 6, 4, 6, 6, 5, 6, 6,
                6, 5, 6, 6, 4, 6, 6, 5, 5, 6, 5, 6, 6, 6, 5, 5, 6, 6, 5, 4, 6, 5, 6, 5, 6, 5, 5, 6, 5, 4, 5, 6, 5, 4, 6, 5, 5, 4, 5, 4, 5, 6, 5, 6, 4, 6, 5, 4,
                4, 4, 5, 5, 4, 5, 4, 6, 4, 5, 5, 6, 5, 6, 6, 5, 4, 6, 6, 5, 5, 6, 5, 5, 5, 5, 6, 5, 5, 4, 4, 6, 4, 5, 4, 6, 6, 5, 6, 5, 6, 6, 4, 5, 5, 5, 5, 6,
                6, 4, 4, 5, 6, 5, 5, 6, 4, 6, 6, 5, 5, 6, 4, 4, 4, 4, 5, 4, 5, 4, 5, 5, 4, 5, 5, 5, 4, 6, 4, 4, 4, 5, 4, 4, 5, 4, 6, 6, 5, 6, 4, 4, 6, 6, 4, 4,
                5, 6, 5, 5, 4, 6, 6, 4, 6, 5, 4, 5, 5, 6, 6, 6, 4, 6, 6, 5, 6, 4, 5, 6, 4, 6, 4, 5, 5, 4, 4, 6, 6, 6, 4, 6, 5, 5, 4, 5, 5, 4, 5, 6, 6, 6, 4, 5,
                4, 5, 6, 4, 6, 4, 5, 4, 5, 4, 6, 6, 6, 5, 4, 6, 4, 6, 4, 5, 6, 5, 6, 6, 6, 5, 4, 5, 6, 6, 6, 6, 4, 5, 6, 5, 4, 4, 5, 5, 4, 4, 4, 5, 4, 6, 6, 6,
                6, 4, 5, 5, 4, 5, 4, 5, 4, 4, 6, 4, 5, 5, 6, 4, 6, 5, 4, 6, 4, 6, 5, 5, 6, 5, 4, 4, 5, 4, 4, 5, 5, 5, 5, 4, 4, 5, 6, 4, 4, 6, 6, 5, 4, 6, 5, 5,
                4, 4, 6, 4, 6, 4, 5, 6, 4, 5, 4, 6, 5, 4, 4, 5, 6, 4, 4, 5, 5, 6, 6, 6, 6, 6, 6, 4, 6, 5, 6, 6, 6, 6, 4, 4, 5, 6, 5, 4, 5, 4, 4, 5, 6, 5, 5, 4,
                4, 4, 6, 6, 6, 6, 6, 4, 5, 4, 4, 4, 4, 5, 6, 4, 4, 5, 5, 6, 6, 6, 6, 4, 6, 6, 5, 4, 6, 4, 5, 4, 5, 5, 4, 6, 6, 4, 6, 4, 5, 4, 5, 5, 4, 6, 5, 5,
                4, 4, 6, 6, 5, 5, 4, 6, 5, 5, 6, 6, 4, 6, 6, 4, 6, 6, 4, 5, 6, 6, 5, 4, 5, 4, 5, 5, 5, 4, 6, 5, 4, 6, 5, 4, 4, 5, 6, 5, 5, 6, 4, 4, 6, 4, 4, 5,
                4, 5, 5, 4, 5, 5, 4, 4, 6, 4, 5, 6, 4, 4, 5, 6, 6, 4, 5, 4, 6, 5, 5, 5, 5, 6, 4, 5, 6, 6, 6, 4, 6, 5, 4, 6, 5, 4, 5, 4, 5, 4, 6, 4, 6, 6, 4, 5,
                6, 4, 4, 6, 5, 4, 4, 5, 6, 6, 4, 6, 6, 4, 6, 5, 6, 6, 4, 4, 5, 5, 6, 5, 4, 4, 5, 4, 5, 4, 4, 6, 4, 4, 4, 4, 4, 4, 6, 6, 6, 5, 6, 5, 5, 4, 5, 5,
                5, 5, 5, 6, 5, 6, 4, 6, 5, 4, 5, 4, 5, 4, 6, 5, 5, 4, 5, 6, 5, 4, 5, 5, 6, 4, 6, 5, 6, 4, 6, 6, 5, 6, 4, 4, 4, 5, 4, 6, 4, 4, 4, 5, 4, 5, 4, 6,
                4, 4, 5, 4, 5, 6, 4, 6, 6, 5, 4, 5, 4, 5, 6, 4, 5, 6, 4, 5, 4, 5, 5, 4, 4, 5, 4, 5, 6, 5, 4, 5, 5, 6, 4, 5, 5, 4, 6, 6, 6, 5, 5, 5, 6, 6, 4, 6,
                5, 4, 6, 6, 6, 5, 6, 6, 4, 4, 5, 6, 4, 4, 5, 6, 5, 5, 5, 6, 6, 5, 4, 6, 6, 5, 4, 5, 6, 4, 4, 6, 4, 6, 4, 4, 5, 4, 5, 4, 5, 4, 6, 4, 5, 5, 6, 5,
                5, 4, 6, 6, 4, 6, 5, 5, 5, 6, 5, 4, 5, 6, 6, 4, 6, 6, 4, 5, 6, 4, 6, 4, 5, 4, 4, 6, 5, 5, 4, 6, 5, 4, 6, 6, 4, 4, 5, 6, 4, 4, 4, 4, 4, 6, 6, 6,
                4, 5, 5, 4, 4, 5, 4, 4, 5, 6, 5, 4, 6, 6, 6, 5, 6, 5, 4, 5, 4, 6, 6, 5, 6, 5, 4, 4, 5, 4, 4, 4, 6, 4, 5, 5, 4, 4, 5, 4, 5, 5, 5, 5, 5, 6, 4, 5,
                4, 4, 4, 4, 4, 4, 5, 4, 6, 5, 5, 4, 4, 5, 5, 4, 4, 5, 5, 6, 4, 6, 4, 5, 5, 6, 5, 5, 6, 4, 4, 5, 5, 6, 5, 4, 4, 4, 4, 4, 6, 5, 4, 5, 6, 4, 4, 6,
                4, 4, 4, 6, 4, 4, 6, 5, 6, 6, 6, 5, 6, 5, 4, 5, 4, 5, 5, 6, 5, 6, 4, 6, 5, 6, 4, 4, 6, 6, 4, 4, 5, 5, 5, 5, 5, 4, 6, 4, 5, 4, 4, 4, 4, 5, 6, 4,
                4, 5, 4, 5, 5, 6, 6, 5, 6, 6, 5, 6, 6, 5, 5, 4, 5, 4, 5, 5, 5, 4, 4, 6, 5, 4, 6, 6, 6, 4, 4, 6, 5, 6, 5, 6, 6, 4, 5, 6, 6, 6, 4, 4, 4, 5, 4, 4,
                6, 5, 5, 6, 4, 6, 4, 6, 4, 4, 4, 5, 6, 6, 6, 6, 5, 6, 5, 5, 4, 4, 6, 4, 6, 4, 4, 6, 6, 5, 4, 4, 6, 5, 4, 5, 4, 4, 6, 6, 6, 5, 5, 5, 6, 6, 6, 4,
                4, 6, 5, 6, 4, 6, 5, 6, 5, 5, 5, 5, 6, 5, 6, 6, 4, 6, 6, 6, 6, 4, 5, 6, 5, 6, 4, 6, 6, 5, 5, 4, 4, 6, 4, 4, 5, 4, 4, 5, 6, 6, 4, 4, 6, 6, 6, 4,
                5, 4, 5, 6, 6, 5, 6, 4, 5, 5, 5, 4, 4, 4, 5, 4, 5, 5, 5, 5, 4, 4, 5, 5, 6, 4, 6, 5, 5, 4, 4, 6, 6, 5, 6, 4, 4, 6, 4, 6, 4, 6, 4, 4, 4, 6, 5, 6,
                4, 6, 5, 4, 4, 6, 4, 6, 6, 4, 5, 6, 6, 4, 4, 4, 4, 6, 5, 4, 4, 5, 5, 6, 6, 5, 4, 4, 4, 6, 6, 5, 5, 5, 6, 4, 5, 4, 5, 5, 4, 4, 6, 5, 4, 5, 4, 6,
                5, 6, 5, 4, 4, 6, 4, 5, 6, 5, 4, 5, 4, 5, 4, 4, 5, 6, 5, 6, 5, 4, 5, 4, 4, 5, 6, 4, 6, 4, 6, 4, 5, 4, 4, 6, 5, 5, 5, 4, 5, 6, 4, 5, 4, 4, 6, 5,
                5, 6, 5, 6, 6, 4, 4, 6, 6, 6, 6, 4, 6, 4, 4, 5, 4, 4, 4, 6, 6, 5, 4, 6, 4, 6, 6, 6, 5, 4, 5, 6, 5, 5, 5, 5, 5, 4, 4, 6, 4, 5, 5, 5, 5, 5, 5, 5,
                4, 6, 4, 6, 6, 4, 5, 4, 4, 6, 5, 6, 5, 4, 4, 6, 5, 6, 5, 6, 5, 5, 6, 6, 6, 5, 4, 4, 4, 5, 4, 6, 6, 5, 5, 4, 6, 5, 6, 6, 5, 4, 4, 5, 4, 6, 5, 4,
                6, 6, 5, 5, 5, 5, 6, 6, 6, 6, 6, 4, 6, 6, 5, 6, 6, 4, 4, 4, 4, 5, 4, 5, 4, 4, 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 5, 4, 6, 4, 4, 5, 5, 5, 6,
                6, 5, 6, 5, 4, 4, 4, 6, 6, 5, 6, 4, 5, 5, 6, 6, 4, 5, 5, 4, 5, 5, 4, 5, 6, 5, 6, 5, 6, 6, 5, 5, 4, 5, 4, 5, 6, 5, 5, 5, 4, 4, 6, 5, 5, 4, 4, 6,
                6, 6, 6, 5, 6, 6, 4, 5, 5, 4, 5, 4, 4, 4, 4, 5, 6, 6, 5, 4, 4, 4, 5, 6, 5, 5, 4, 4, 6, 5, 4, 6, 4, 4, 4, 4, 5, 6, 4, 5, 5, 4, 5, 4, 5, 6, 5, 5,
                4, 5, 6, 4, 5, 4, 4, 4, 6, 5, 4, 5, 6, 4, 5, 4, 4, 4, 5, 5, 5, 6, 6, 4, 4, 6, 6, 4, 4, 5, 5, 6, 4, 6, 6, 6, 6, 4, 5, 6, 4, 6, 6, 6, 5, 6, 5, 6,
                5, 5, 5, 5, 5, 5, 5, 4, 6, 5, 4, 4, 6, 6, 6, 6, 6, 4, 5, 4, 6, 4, 5, 5, 6, 6, 5, 5, 6, 6, 5, 6, 5, 6, 4, 5, 4, 5, 4, 5, 6, 5, 4, 5, 5, 6, 4, 4,
                6, 6, 6, 6, 5, 5, 6, 4, 6, 4, 6, 6, 6, 6, 4, 6, 5, 4, 6, 4, 4, 5, 6, 6, 6, 6, 4, 5, 6, 4, 6, 4, 4, 4, 6, 6, 4, 5, 6, 4, 6, 6, 5, 6, 6, 6, 5, 5,
                4, 4, 5, 5, 5, 6, 5, 6, 6, 6, 6, 6, 5, 5, 5, 6, 4, 5, 6, 5, 4, 4, 5, 4, 5, 5, 4, 4, 6, 4, 4, 6, 4, 5 };
        int k = 90000;
        System.out.println(woodCut(L, k));
    }
}
